#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;

//让字符串成为回文串的最少插入次数
//https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/submissions/
// class Solution {
// public:
//     int minInsertions(string s) {
//         int n = s.size();
//         vector<vector<int>> vv(n,vector<int>(n));

//         for(int i = n-1;i>=0;--i)
//             //我们可能用到下面的值[i+1] 和 左边的值[k-1] vv[i+1][k-1]
//             //所以填表需要从下往上从左往右填
//             for(int k = i+1;k<n;++k)
//             {
//                 //i==k时一定相等不需要插入 插入次数为0 
//                 if(s[i] == s[k]) vv[i][k] = vv[i+1][k-1];
//                 //当不相等时 查看s[i+1]==s[k] s[i]==s[k-1]两个区间
//                 else vv[i][k] = min(vv[i+1][k],vv[i][k-1])+1;    
//             }
//         return vv[0][n-1];
//     }
// };


//最长公共子序列
//https://leetcode.cn/problems/longest-common-subsequence/description/
// class Solution {
// public:
//     int longestCommonSubsequence(string text1, string text2) {
//         int n1 = text1.size();
//         int n2 = text2.size();

//         //vv[i][k] 表示：
//         //s1字符串以i结尾 s2字符串以k结尾时 最长公共子序列
//         //当 s1[i] == s2[k] 时 公共子序列为s[i-1][k-1]+1
//         //当 s1[i] != s2[k] 时 
//         //[i][k-1] [i-1][k] [i-1][k-1] 这三个区间中可能存在公共子序列
//         //其中[i][k-1] [i-1][k]包含[i-1][k-1]情况 所以第三个情况可以忽略不计
//         vector<vector<int>> vv(n1+1,vector<int>(n2+1));

//         for(int i = 1;i<=n1;++i)
//             for(int k = 1;k<=n2;++k)
//             {
//                 if(text1[i-1] == text2[k-1]) vv[i][k] = vv[i-1][k-1]+1;
//                 else vv[i][k] = max(vv[i-1][k],vv[i][k-1]);
//             }

//         return vv[n1][n2];
//     }
// };


//不相交的线(最长公共子序列转化问题)
//https://leetcode.cn/problems/uncrossed-lines/description/
// class Solution {
// public:
//     int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
//         int n1 = nums1.size();
//         int n2 = nums2.size();

//         //将连线问题转化为最长公共子序列问题
//         vector<vector<int>> vv(n1+1,vector<int>(n2+1));

//         for(int i = 1;i<=n1;++i)
//             for(int k = 1;k<=n2;++k)
//             {
//                 if(nums1[i-1] == nums2[k-1]) vv[i][k] = vv[i-1][k-1]+1;
//                 else vv[i][k] = max(vv[i-1][k],vv[i][k-1]);
//             }

//         return vv[n1][n2];
//     }
// };